package com.abel.day0309;

import com.abel.day0301.TreeNode;

import java.util.*;

/**
 * @author xiachao
 * @date 2019/3/9
 */
public class Solution {

    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null){
            return true;
        }
        return same(pRoot.left, pRoot.right);
    }

    boolean same(TreeNode r1, TreeNode r2){
        if(r1 == null && r2 == null){
            return true;
        }
        if(r1 == null) return false;
        if(r2 == null) return false;
        if(r1.val != r2.val) return false;
        return same(r1.left, r2.right) & same(r1.right, r2.left);
    }

    public ArrayList<ArrayList<Integer>> Print0(TreeNode pRoot) {
        if(pRoot == null){
            return null;
        }
        ArrayList<TreeNode> current = new ArrayList<TreeNode>();
        current.add(pRoot);
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        int n = 1;
        while(!current.isEmpty()){
            ArrayList<Integer> arr = new ArrayList<Integer>();
            ArrayList<TreeNode> tmp = new ArrayList<TreeNode>();
            for(int i=0;i<current.size();i++){
                TreeNode node = current.get(i);
                if(node.left!=null){
                    tmp.add(node.left);
                }
                if(node.right!=null){
                    tmp.add(node.right);
                }
                arr.add(node.val);
            }
            ArrayList<Integer> arr2 = new ArrayList<Integer>();
            if(n % 2 == 1){
                for(int i=0;i<arr.size();i++){
                    arr2.add(arr.get(i));
                }
            }else{
                for(int i=arr.size()-1;i>=0;i--){
                    arr2.add(arr.get(i));
                }
            }
            n++;
            ret.add(arr2);
            current.clear();
            current.addAll(tmp);
        }
        return ret;
    }

    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if(pRoot == null){
            return new ArrayList<ArrayList<Integer>>();
        }
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> queue = new LinkedList();
        queue.add(pRoot);
        while(!queue.isEmpty()){
            Queue<TreeNode> tmp = new LinkedList<TreeNode>();
            ArrayList<Integer> arr = new ArrayList<Integer>();Collections.sort(arr);
            while(!queue.isEmpty()){
                TreeNode n = queue.poll();
                if(n.left != null){
                    tmp.add(n.left);
                }
                if(n.right != null){
                    tmp.add(n.right);
                }
                arr.add(n.val);
            }
            queue.clear();
            queue = tmp;
            if(!arr.isEmpty()){
                ret.add(arr);
            }
        }

        return ret;
    }

    String Serialize(TreeNode root) {
        return null;
    }
    TreeNode Deserialize(String str) {
        return null;
    }

    TreeNode KthNode(TreeNode pRoot, int k) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preTravel(pRoot, list);
        if(list.size() < k){
            return null;
        }
        return list.get(k-1);
    }

    void preTravel(TreeNode root, List<TreeNode> list){
        if(root == null){
            return;
        }
        list.add(root);
        preTravel(root.left, list);
        preTravel(root.right, list);
    }

}
